#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

// 直观思路 时间复杂度O(n^2) 超时了
int minSubArrayLen(int target, vector<int>& nums) {
    int result = 0;
    for (int i = 0, len = nums.size(); i < len; i++) {
        int sum = 0;
        for (int j = i; j < len; j++) {
            sum += nums[j];
            if (sum >= target) {
                if (result == 0 || j - i + 1 < result) {
                    result = j - i + 1;
                }
                break;
            }
        }
    }

    return result;
}

// 滑动窗口（双指针）
// 时间复杂度为O(n)
/**
 * 不要以为for里放一个while就以为是O(n^2)， 
 * 主要是看每一个元素被操作的次数，
 * 每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，
 * 所以时间复杂度是 2 × n 也就是O(n)。
*/
int minSubArrayLen2(int target, vector<int>& nums) {
    int len = nums.size();
    int result = len + 1;
    int sum = 0;
    for (int left = 0, right = 0; right < len; right++) {
        sum += nums[right];
        while (sum >= target) {
            int subL = right - left + 1;
            result = min(result, subL);
            sum -= nums[left];
            left++;
        }
    }

    return result == len + 1 ? 0 : result;
}

int main() {
    vector<int> nums = {1,1,1,1,100};
    int target = 100;
    int result = minSubArrayLen2(target, nums);

    cout << "result = " << result << endl;
}